package number_321;

import java.util.LinkedList;

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int n1 = nums1.length, n2 = nums2.length;
        int[] res = new int[k];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i <= k; i++) {
            if (i <= n1 && k - i <= n2) {
                int[] maxNum1 = getMaxNum(nums1, i);
                int[] maxNum2 = getMaxNum(nums2, k - i);
                int[] maxNumber = merge(maxNum1, maxNum2, k);
                int n = maxNumber.length - 1;
                int sum = 0;
                for (int v : maxNumber) {
                    sum += v * Math.pow(10, n--);
                }
                if (sum > max) {
                    max = sum;
                    res = maxNumber;
                }
            }
        }
        return res;
    }

    private int[] merge(int[] nums1, int[] nums2, int k) {
        int[] res = new int[k];
        for (int i = 0, j = 0, r = 0; r < k; r++) {
            res[r] = greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++];
        }
        return res;

    }

    private boolean greater(int[] nums1, int i, int[] nums2, int j) {
        while (i < nums1.length && j < nums2.length && nums1[i] == nums2[j]) {
            i++;
            j++;
        }
        return j == nums2.length || (i < nums1.length && nums1[i] > nums2[j]);

    }

    private int[] getMaxNum(int[] nums, int k) {
        if (k == 0) {
            return new int[0];
        }
        if (k == nums.length) {
            return nums;
        }
        LinkedList<Integer> stack = new LinkedList<>();
        int n = nums.length;
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            while (stack.size() > 0 && nums[i] > stack.peekLast() && n - j > k) {
                stack.pollLast();
                j++;
            }
            stack.addLast(nums[i]);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = stack.get(i);
        }
        return res;

    }
}
